In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters.

This report investigates the problem of learning rate optimisation, focusing on techniques that remove the programmer's burden to choose a proper initial learning rate. The report aims to satisfy two purposes: 1. Acting as an intuition-led guide to Defazio and Mishchenko's 2023 Learning-Rate-Free Learning by D-Adaptation [2] and Mahsereci and Hennig's 2015 Probabilistic Line Searches for Stochastic Optimisation [5]. 2. Presenting a unified notation to discuss optimisation techniques, allowing us to bring together the two learning-rate-free approaches and introduce probabilistics to D-Adaptation in the Discussion section (4). We will begin by recapping the general problem of optimisation. This will establish a common language through which to discuss optimisation algorithms, and introduce the notation used in Defazio et al's D-Adaptation paper.

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters.

In deterministic optimization, line searches are a standard tool ensuring stability and efficiency. Where only stochastic gradients are available, no direct equivalent has so far been formulated, because uncertain gradients do not allow for a strict sequence of decisions collapsing the search space. We construct a probabilistic line search by combining the structure of existing deterministic methods with notions from Bayesian optimization. Our method retains a Gaussian process surrogate of the univariate optimization objective, and uses a probabilistic belief over the Wolfe conditions to monitor the descent. The algorithm has very low computational cost, and no user-controlled parameters. Experiments show that it effectively removes the need to define a learning rate for stochastic gradient descent.